<html>
<head>
 <title>Recursive Ant</title>
</head>

<body>

<center>
<h1>POI IV Stage II Problem 5</h1>
<h1>Recursive Ant</h1>
</center>

<P>
Consider a chessboard of size 2<sup>n</sup> x 2<sup>n</sup>.
Some of its squares are  marked and called <b>forbidden squares</b>. An ant
is going to visit all squares of the chessboard except the forbidden
ones. Each of the squares has to be visited exactly once.

The tour begins in the start square, which is the top-left square of
the board and has to finish in one of the periphery squares
(the ant want to leave the board in the end). We assume that the start square is not
forbidden. In a single step the ant can move to one of at most
four neighbouring squares (i.e. she can move up, down, left or right).
</p>

<p>
The walk of our ant is recursive in a sense: to round the square
of size 2<sup>k</sup> x 2<sup>k</sup> the ant splits it into four
parts (quarters) of size 2<sup>k-1</sup> x 2<sup>k-1</sup> and then rounds 
each of them. It means if the ant enters one of the quarters she cannot 
leave it before visiting all the squares in this quarter that are not 
forbidden.</p>

<p>In the Figure 1 you can see two routes of a recursive tour of the ant
on the board of size 2<sup>3</sup> x 2<sup>3</sup>. 
Both routes begin in the start square (0,0). First of
them is finished in the top periphery and the second in the left periphery of the 
board.

<p>
<center>
<img src="image/163.gif" alt="Ant route"><br>
<i>Figure 1</i></center>
</p>


<p>
<h2>Task</h2>
Write a program that:
<ul>
<li>reads positive integers n and m from the text file REK.IN; n
describes the size of the board 2<sup>n</sup> x 2<sup>n</sup>, m
is the number of forbidden squares; then reads coordinates of all
forbidden squares,
<li>for each of the four peripheries of the board finds a square 
at which a recursive tour described before can be finished
or states that such a square does not exist,
<li>writes the result to the text file REK.OUT.
</ul>
Note: each of the four squares in the corners of the board belongs to
two peripheries. 
</p>
 
<p>
<h2>Input</h2>
In the first line of the text file REK.IN there is one positive integer n
&lt;= 30. </p>

<p>In the second line there is the number of forbidden squares m,
m &lt;= 50.</p>

<p>In each of the following m lines there is a pair of non-negative
integers i, j separated by a single space; i and j are coordinates
of a forbidden square (i is the number of line and j is the number
of column). The lines and columns of the board are numbered from
0 to 2<sup>n</sup>-1. The top-left square has coordinates (0,0).
</p>
 
<p>
<h2>Output</h2>
In each of four consecutive lines of the text file REK.OUT there
should be written two non-negative integers separated by a single 
space. These integers should be coordinates (the number of line and column) of the end
square of an appropriate tour. If such a square does not exists
the word NIE (which means NO in
Polish) should be written. In the first line there should be
the square of the tour ending on the top periphery, in the second 
- on the right periphery, in the third - on the bottom periphery and
in the fourth line - on the left periphery.  
</p>
 
<p>
<h2>Example</h2>
For the file REK.IN (describing the board shown in the figure):
<pre>3
15
2 0
1 0
3 0
6 0
7 0
6 1
7 1
6 2
7 2
6 3
7 3
0 2
0 3
0 6
0 7
1 6
1 7</pre>
the correct result is the file REK.OUT
<pre>0 4
NIE
NIE
4 0</pre>
</p>
 
</body>
</html>
